public class test01 {
    public int LIS (int[] arr) {
        // write code here
        int n = arr.length;
        if (n == 0) {
            return 0;
        }

        // tails 数组的长度就是最长上升子序列的长度
        int[] tails = new int[n];
        int size = 0;

        for (int num : arr) {
            int left = 0, right = size;
            // 使用二分查找来找到 num 应插入的位置
            while (left < right) {
                int mid = left + (right - left) / 2;
                if (tails[mid] < num) {
                    left = mid + 1;
                } else {
                    right = mid;
                }
            }
            // 如果 left == size，说明 num 大于 tails 数组中的所有元素
            tails[left] = num;
            if (left == size) {
                size++;
            }
        }

        return size;
    }
}
